package leetcode_2401_2500;

import com.sun.org.apache.bcel.internal.generic.IRETURN;
import javafx.util.Pair;

import java.util.*;

public class LeeCode_2402 {
    public static void main(String[] args) {
        System.out.println(mostBooked(2, new int[][]{{0, 10}, {1, 5}, {2, 7}, {3, 4}}));
        System.out.println(mostBooked(3, new int[][]{{1, 20}, {2, 10}, {3, 5}, {4, 9}, {6, 8}}));
        System.out.println(mostBooked(3, new int[][]{{3, 7}, {12, 19}, {16, 17}, {1, 17}, {5, 6}}));
    }

    private static int mostBooked(int n, int[][] meetings) {
        int[] cnt = new int[n];
        PriorityQueue<Integer> idle = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            idle.offer(i);
        }
        PriorityQueue<Pair<Long, Integer>> using = new PriorityQueue<>((a, b) ->
                !Objects.equals(a.getKey(), b.getKey()) ? Long.compare(a.getKey(), b.getKey()) : Integer.compare(a.getValue(), b.getValue()));
        Arrays.sort(meetings, Comparator.comparingInt(o -> o[0]));
        for (int[] meeting : meetings) {
            long st = meeting[0], end = meeting[1];
            while (!using.isEmpty() && using.peek().getKey() <= st){
                idle.offer(using.poll().getValue());
            }
            if (idle.isEmpty()){
                Pair<Long, Integer> p = using.poll();
                idle.offer(p.getValue());
                end =  p.getKey() + end - st;
            }
            Integer p = idle.poll();
            using.add(new Pair<>(end, p));
            cnt[p]++;
        }
        int ans = 0, max = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] > max) {
                max = cnt[i];
                ans = i;
            }
        }
        return ans;
    }
}